#pragma once
#include <iostream>
#include <assert.h>
#include <cmath>

using namespace std;

template <class K, class V>
struct AVLTreeNode {
    AVLTreeNode<K, V> *_left;
    AVLTreeNode<K, V> *_right;
    AVLTreeNode<K, V> *_parent;
    
    pair<K, V> _kv;
    int _bf;        //balance factor = 右子树 - 左子树

    AVLTreeNode(const pair<K, V>& kv)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _bf(0)
    {}
};

template <class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
private:
    Node* _root;
public:
    AVLTree()
        :_root(nullptr)
    {}
    bool Insert(const pair<K, V>& kv)
    {
        if(_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while(cur)
        {
            if(kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            } 
            else 
            {
                return false;
            }
        }
        cur = new Node(kv);
        if(cur->_kv.first < parent->_kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else 
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        //控制树的平衡
        //1、更新平衡因子
        while(parent)
        {
            if(cur == parent->_left)
            {
                parent->_bf--;
            }
            else 
            {
                parent->_bf++;
            }

            //2、检查父亲的平衡因子
            //（1）父亲所在子树高度不变，不影响祖先，更新结束
            if(parent->_bf == 0)
            {
                break;
            }//（2）父亲所在子树高度变了，继续向上更新
            else if(parent->_bf == -1 || parent->_bf == 1)
            {
                cur = parent;
                parent = cur->_parent; 
            }//（3）父亲的子树出现了不平衡，需要旋转处理
            else if(parent->_bf == -2 || parent->_bf == 2)
            {
                if(cur->_bf == -1 && parent->_bf == -2)
                {
                    //左左——右单旋
                    RoutateR(parent);
                }
                else if(cur->_bf == 1 && parent->_bf == 2)
                {
                    //右右——左单旋 
                    RoutateL(parent);
                }
                else if(cur->_bf == 1 && parent->_bf == -2)
                {
                    RoutateLR(parent);
                }
                else if(cur->_bf == -1 && parent->_bf == 2)
                {
                    RoutateRL(parent);
                }
                else 
                {
                    assert(false); 
                }
                break;
            }
            else 
            {
                assert(false);
            }
        }
        return true;
    }

    void RoutateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if(subLR != nullptr)
        {
            subLR->_parent = parent;
        } 
        Node* ppNode = parent->_parent;

        subL->_right = parent;
        parent->_parent = subL;     /*如果parent是根，那么它的父节点是空，这样会不会奇怪*/
        //所以需要单独判断，subL可能只是子树的根，也可能是整棵树的根
        if(parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else 
        {
            if(ppNode->_left == parent)
            {
                ppNode->_left = subL;
            }
            else 
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
        subL->_bf = 0;
        parent->_bf = 0; 
    }

    void RoutateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if(subRL != nullptr)
        {
            subRL->_parent = parent;
        }

        Node* ppNode = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;

        if(parent == _root)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else 
        {
            if(parent == ppNode->_left)
            {
                ppNode->_left = subR;
            }
            else 
            {
                ppNode->_right = subR;
            }
            subR->_parent = ppNode;
        }
        subR->_bf = 0;
        parent->_bf = 0;
    }

    void RoutateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
        RoutateL(parent->_left);
        RoutateR(parent);
        if(bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else if(bf == 1)
        {
            parent->_bf = 0;
            subL->_bf = -1;
            subLR->_bf = 0;
        }
        else if(bf == 0)
        {
            parent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        else 
        {
            assert(false);
        }
    }

    void RoutateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RoutateR(parent->_right);
        RoutateL(parent);

        if(bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }
        else if(bf == 1)
        {
            parent->_bf = -1;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else if(bf == 0)
        {
            parent->_bf = 0;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else 
        {
            assert(false);
        }
    }

    bool IsBalance()
    {
        return _IsBalance(_root);
    }

    ~AVLTree(){}

private:
    bool _IsBalance(Node* root)
    {
        if(root == nullptr)
        {
            return true;
        }
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        if(rightHeight - leftHeight != root->_bf)
        {
            cout << "平衡因子异常" << endl;
        }
        return abs(leftHeight - rightHeight) < 2
        && _IsBalance(root->_left)
        && _IsBalance(root->_right);
    }

    int Height(Node* root)
    {
        if(root == nullptr)
        {
            return 0;
        }
        int leftHeight = Height(root->_left);
        int rightHeight = Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
};

void TestAVLTree1()
{
    AVLTree<int, int> t1;
    t1.Insert(make_pair(1, 1));
    t1.Insert(make_pair(2, 2));
    t1.Insert(make_pair(3, 3));
    t1.Insert(make_pair(4, 4));
    t1.Insert(make_pair(5, 5));
    t1.Insert(make_pair(6, 6));
    cout << t1.IsBalance() << endl;
}

void TestAVLTree2()
{
       int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    // int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    AVLTree<int, int> t1;
    for(auto e: a)
    {
        t1.Insert(make_pair(e, e));
    }
    cout << t1.IsBalance() << endl;
}